package com.caoyanan.algorithm.question.zuoTraining.training003.class07;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 求range缺失数
 *  给定一个有序的正数数组arr和一个正数range，如果可以自由选择arr中的数字，想累加得 到 1~range 范围上所有的数，返回arr最少还缺几个数。
 * 【举例】
 * arr = {1,2,3,7}，range = 15
 * 想累加得到 1~15 范围上所有的数，arr 还缺 14 这个数，所以返回1 arr = {1,5,7}，range = 15
 * 想累加得到 1~15 范围上所有的数，arr 还缺 2 和 4，所以返回2
 * @author: caoyanan
 * @time: 2021/5/19 6:24 下午
 */
public class Question03_RangeMinLackNumber {

    public static void main(String[] args) {

        int count = 10000;
        for (int i = 0; i < count; i++) {
            int[] arr = LogarithmInputGenerator.getInstance().generateRandomArray(5, 8);
            int[] result = rangeMinLackNumber(arr, 20).stream().mapToInt(it -> it).toArray();
            System.out.printf("数组 %s 得到累加 1~20 所有数需要新增 %s\r\n", Arrays.toString(arr), Arrays.toString(result));
        }
    }

    private static List<Integer> rangeMinLackNumber(int[] arr, int aim) {
        Arrays.sort(arr);

        long range = 0;
        int needNumber = 0;
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {

            while (arr[i] > range + 1) {
                needNumber ++;
                result.add((int) (range+1));
                range += range +1;
                if (range >= aim) {
                    return result;
                }
            }
            range += arr[i];
            if (range >= aim) {
                return result;
            }
        }
        while (range < aim) {
            needNumber++;
            result.add((int) (range+1));
            range += range+1;
        }
        return result;
    }
}
